#ifdef KITSCHY_DEBUG_MEMORY 
#include "debug_memorymanager.h"
#endif

#ifdef WIN32
#include "windows.h"
#else
#include <sys/time.h>
#include <time.h>
#endif
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "stdarg.h"
#include "math.h"

#include "BList.h"

#include "symbol.h"
#include "sort.h"
#include "ontology.h"
#include "featureterm.h"
#include "FTKBase.h"
#include "AUfeatureterm.h"
#include "FT_refinement.h"
#include "FT_generalization.h"

#include "psm.h"
#include "rFOIL.h"


/* 

	Since FOIL is basically a concept learning method, we implement HYDRA.
	HYDRA is a relational learning algorithm based on FOIL that learns a different rule for each solution class.
	Then, it computes a reliability measure for each rule, that is use to resolve ties during problem solving.
	Reliability is computes using the Laplace estimator of the accuracy of a rule, i.e.: (p+1)/(p+n+2)
	If a problem is not covered by any rule, it is assigned the most frequent solution class.

*/ 
bool rFOILHypothesis::learn(List<FeatureTerm> *cases,Path *description_path,Path *solution_path,Ontology *o,FTKBase *domain_model,int heuristic)
{
	FeatureTerm *solution;
	List<FeatureTerm> solutions;
	List< List<FeatureTerm> > descriptions;

	/* Compute the different solutions: */ 
	{
		int pos;
		FeatureTerm *c,*s,*d;
		List<FeatureTerm> l,*tmp;

		l.Instance(*cases);
		while(l.Iterate(c)) {
/*
			{
				char *s=c->toStringNOOS(domain_model);
				printf("%s\n",s);
				delete []s;
			}
*/			
			tmp=c->readPath(description_path);
			if (tmp->Length()==1) d=tmp->ExtractIni();
							 else d=0;
			delete tmp;
			tmp=c->readPath(solution_path);
			if (tmp->Length()==1) s=tmp->ExtractIni();
							 else s=0;
			delete tmp;
			
			pos=solutions.Position(s);
			if (pos==-1) {
				solutions.Add(s);
				tmp=new List<FeatureTerm>;
				tmp->Add(d);
				descriptions.Add(tmp);
			} else {
				delete s;
				descriptions[pos]->Add(d);
			} /* if */ 
		} /* while */ 
	}

	/* Compute the default solution: */ 
	{
		int max=-1;
		FeatureTerm *s;
		List<FeatureTerm> *tmp;

		m_default_solution=0;

		solutions.Rewind();
		descriptions.Rewind();

		while(solutions.Iterate(s) &&  descriptions.Iterate(tmp)) {
			if (max==-1 || tmp->Length()>max) {
				max=tmp->Length();
				delete m_default_solution;
				m_default_solution=new FeatureTerm(s);
			} /* if */ 
		} /* while */ 
	}

	solutions.Rewind();
	while(solutions.Iterate(solution)) {
		learn_single_class(solution,cases,description_path,solution_path,o,domain_model,heuristic);
	} /* while */ 

	return true;
} /* rFOILHypothesis::learn */ 


bool rFOILHypothesis::learn_single_class(FeatureTerm *solution,List<FeatureTerm> *cases,Path *description_path,Path *solution_path,Ontology *o,FTKBase *domain_model,int heuristic)
{
	List<FeatureTerm> positive;
	List<FeatureTerm> negative;

	/* Learn a set of patterns for the current solution: */ 
	{
		char *s=solution->toStringNOOS(domain_model);
		printf("\nrFOIL: building model for %s --------------------------------------------------\n\n",s);
		delete []s;
	}

	/* Create the positive and negative examples lists: */ 
	{
		FeatureTerm *c,*s,*d;
		List<FeatureTerm> l,*tmp;

		l.Instance(*cases);
		while(l.Iterate(c)) {
/*
			{
				char *s=c->toStringNOOS(domain_model);
				printf("%s\n",s);
				delete []s;
			}
*/			
			tmp=c->readPath(description_path);
			if (tmp->Length()==1) d=tmp->ExtractIni();
							 else d=0;
			delete tmp;
			tmp=c->readPath(solution_path);
			if (tmp->Length()==1) s=tmp->ExtractIni();
							 else s=0;
			delete tmp;

			if (solution->equivalents(s)) {
				positive.Add(d);
			} else {
				negative.Add(d);
			} /* if */ 
			delete s;
		} /* while */ 
	}

	printf("%i positives and %i negatives\n",positive.Length(),negative.Length());

	if (negative.EmptyP()) {
		FeatureTerm *pattern=new FeatureTerm((Symbol *)0,o->get_sort("any"),0);

		printf("rFOIL: rule found, covers %i positive examples\n",positive.Length());
		{
			char *s1,*s2;
			s1=solution->toStringNOOS(domain_model);
			s2=pattern->toStringNOOS(domain_model);
			printf("rFOIL: rule is for class %s,\n%s\n\n",s1,s2);
			delete []s1;
			delete []s2;
		}

		m_patterns.Add(pattern);
		m_solutions.Add(new FeatureTerm(solution));
		m_reliability.Add(new float(1));
	} else {
		FeatureTerm *pattern,*refinement;
		List<FeatureTerm> *refinements;
		int i,selected,nrefinements;
		float *heuristics;
		int *coverage;

		pattern=0;

		/* Build patterns until all the positive examples have been covered: */ 
		while(!positive.EmptyP()) {
//				printf("rFOIL: %i positive, %i negative\n",positive.Length(),negative.Length());

			if (pattern==0) pattern=new FeatureTerm((Symbol *)0,o->get_sort("any"),0);

/*
			{
				char *s;
				s=pattern->toStringNOOS(domain_model);
				printf("%s\n",s);
				delete []s;
			}
*/				
			refinements = DSpecializationL2_b(pattern,&positive,0,o,domain_model);

			/* Filter refinements: */ 
			{
				List<FeatureTerm> to_delete;

				refinements->Rewind();
				while(refinements->Iterate(refinement)) {
					if (refinement->subsumes(pattern)) to_delete.Add(refinement);
				} /* while */ 

				while(!to_delete.EmptyP()) {
					refinement=to_delete.ExtractIni();
					refinements->DeleteElement(refinement);
					delete refinement;
				} /* while */ 
			}

//				printf("rFOIL: %i refinements\n",refinements->Length());

			if (refinements->EmptyP()) {
				int positive_covered=0;
				int negative_covered=0;
				float reliability=0;
				FeatureTerm *f;

				delete refinements;

				positive.Rewind();
				while(positive.Iterate(f)) if (pattern->subsumes(f)) positive_covered++;
				negative.Rewind();
				while(negative.Iterate(f)) if (pattern->subsumes(f)) negative_covered++;
				reliability=float(positive_covered+1)/float(positive_covered+negative_covered+2);

				printf("rFOIL: rule cannot be specified further, covers %i positive examples and %i negative examples\n",positive_covered,negative_covered);
				{
					char *s1,*s2;
					s1=solution->toStringNOOS(domain_model);
					s2=pattern->toStringNOOS(domain_model);
					printf("rFOIL: rule is for class %s,\n%s\n\n",s1,s2);
					delete []s1;
					delete []s2;
				}
				positive.Delete();
				m_patterns.Add(pattern);
				m_solutions.Add(new FeatureTerm(solution));
				m_reliability.Add(new float(reliability));
			} else {
				nrefinements=refinements->Length();
				heuristics=new float[nrefinements];
				coverage=new int[nrefinements];

				/* Compute heuristic: */ 
				i=0;
				refinements->Rewind();
				while(refinements->Iterate(refinement)) {
/*
					{
						char *s;
						s=refinement->toStringNOOS(domain_model);
						printf("%s\n",s);
						delete []s;
					}
*/
					switch(heuristic) {
					case 0:	/* Information Gain: */ 
							{
								int before_p=0,before_n=0;
								int after_p=0,after_n=0;
								float before_i,after_i;
								FeatureTerm *f;
								double LOG2E=log(2.0);

								positive.Rewind();
								while(positive.Iterate(f)) {
									if (pattern->subsumes(f)) before_p++;
									if (refinement->subsumes(f)) after_p++;
								} /* if */ 
								negative.Rewind();
								while(negative.Iterate(f)) {
									if (pattern->subsumes(f)) before_n++;
									if (refinement->subsumes(f)) after_n++;
								} /* if */ 

								before_i=float(-(log(float(before_p)/float(before_p+before_n))/LOG2E));
								if (after_p+after_n==0) after_i=0;
												   else after_i=float(-(log(float(after_p)/float(after_p+after_n))/LOG2E));

//									heuristics[i]=(after_p+after_n)*(before_i-after_i);
//									coverage[i]=after_p+after_n;

								heuristics[i]=(after_p)*(before_i-after_i);
								coverage[i]=after_p;
//									printf("%g = (%i+%i)*(%g - %g)\n",heuristics[i],after_p,after_n,before_i,after_i);
							}
							break;
					case 1: /* RLDM: */ 
							heuristics[i]=0;
							coverage[i]=0;
							break;
					default:heuristics[i]=0;
							coverage[i]=0;
							break;
					} /* switch */ 
					i++;
				} /* while */ 

				{
					float maximum=0;
					selected=-1;

					for(i=0;i<nrefinements;i++) {
						if (coverage[i]>0 &&
							(selected==-1 || heuristics[i]>maximum)) {
							maximum=heuristics[i];
							selected=i;
						} /* if */ 
					} /* for */  

//						printf("Selected: %i (%g)\n",selected,maximum);

					if (selected>=0) {
						int positive_covered=0;
						int negative_covered=0;
						float reliability=0;
						FeatureTerm *f;
						List<FeatureTerm> to_delete;

						delete pattern;
						pattern=new FeatureTerm(*(refinements->operator [](selected)));
						
						positive.Rewind();
						while(positive.Iterate(f)) if (pattern->subsumes(f)) {
							positive_covered++;
							to_delete.Add(f);
						} /* whiel */ 
						negative.Rewind();
						while(negative.Iterate(f)) if (pattern->subsumes(f)) negative_covered++;
						reliability=float(positive_covered+1)/float(positive_covered+negative_covered+2);

						if (negative_covered==0) {
							printf("rFOIL: rule found, covers %i positive examples\n",positive_covered);
							{
								char *s1,*s2;
								s1=solution->toStringNOOS(domain_model);
								s2=pattern->toStringNOOS(domain_model);
								printf("rFOIL: rule is for class %s,\n%s\n\n",s1,s2);
								delete []s1;
								delete []s2;
							}

							while(!to_delete.EmptyP()) {
								f=to_delete.ExtractIni();
								positive.DeleteElement(f);
								delete f;
							} /* while */ 
							m_patterns.Add(pattern);
							m_solutions.Add(new FeatureTerm(solution));
							m_reliability.Add(new float(reliability));
							pattern=0;
						} else {
							while(!to_delete.EmptyP()) to_delete.ExtractIni();
						} /* if */ 
					} else {
						int positive_covered=0;
						int negative_covered=0;
						float reliability=0;
						FeatureTerm *f;

						positive.Rewind();
						while(positive.Iterate(f)) if (pattern->subsumes(f)) positive_covered++;
						negative.Rewind();
						while(negative.Iterate(f)) if (pattern->subsumes(f)) negative_covered++;
						reliability=float(positive_covered+1)/float(positive_covered+negative_covered+2);

						printf("rFOIL: rule cannot be specified further covering some positive , covers %i positive examples and %i negative examples\n",positive_covered,negative_covered);
						{
							char *s1,*s2;
							s1=solution->toStringNOOS(domain_model);
							s2=pattern->toStringNOOS(domain_model);
							printf("rFOIL: rule is for class %s,\n%s\n\n",s1,s2);
							delete []s1;
							delete []s2;
						}
						positive.Delete();
						m_patterns.Add(pattern);
						m_solutions.Add(new FeatureTerm(solution));
						m_reliability.Add(new float(reliability));

						positive.Delete();
					} /* if */ 
				}

				delete []heuristics;
				delete []coverage;
				delete refinements;
			} /* if */ 
		} /* while */ 
	}

	return true;
} /* rFOILHypothesis::learn_single_class */ 


